package 动态规划_斐波那列;

public class 整数拆分_343 {

	/**
	 * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

	示例 1:
	
	输入: 2
	输出: 1
	解释: 2 = 1 + 1, 1 × 1 = 1。
	 输入: 4
	 输出: 4
	 解释: 4 = 2 + 2, 2 × 2 = 4。
	示例 2:
	
	输入: 10
	输出: 36
	解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
	说明: 你可以假设 n 不小于 2 且不大于 58。
	 */
	
	public int integerBreak(int n) {
	    int[] dp = new int[n + 1];//定义一个n+1的数组,因为N拆分最少需要2个数值
	    dp[1] = 1;
	    //从2开始
	    for(int i = 2; i <= n; i++) {
	    	
	        for(int j = 1; j <= i - 1; j++) {
	        							//需要最大,所以可能dp[i-j]那个时候可能还为1
	        	dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
	        }
	    }
	    return dp[n];
	}
	
	/**
	 * 这道题的难点其实在于证明为什么拆出足够多的 33 就能使得乘积最大。下面我就试着证明一下。

	首由均值不等式(n个数的算术平均数大于等于它们的几何平均数)：
	
	(x1+x2+....+xn)   >=   开根号N(x1*x2*.....*xn)
	
	得：当把输入的n拆分成几个相等的数时它们的积最大。
	
	那么问题来了，拆分成几个呢？
	
	为了方便使用导数，我们先假设我们可以把n拆分成实数。那么设每一个数为x,则一共有n/x个数。
	
	设它们的积为f(x),则f(x)=x(n/x)，那么怎么求f(x)最大值呢？求导数！
	
	f′(x)=(n/x2)  *  x(n/x)  * (1-lnx)
	
	当x=e时取极大值。
	
	而我们题目里规定x为整数，那么我们只需要取的x越靠近e越好。那么2<e<3，而且e=2.71828...，所以取3是最好的，如果取不到3就取2。
	 */
	
	public int integerBreak2(int n) {
	    if(n==2) return 1; //1*1
	    if(n==3) return 2; //1*2
		int ret =1;
	    while(n>4) {
	    	ret *=3;
	    	n -=3;
	    }
	    //返回剩余的n 一定为<=3
	    return ret*n;
		
	}
}
